package leetCode.fourthWeek;

import java.util.LinkedList;
import java.util.List;

public class Code_93 {
  List<String> res = new LinkedList<>();

  public List<String> restoreIpAddresses(String s) {
    dfs(s, 0, new LinkedList<>());
    return res;
  }

  public void dfs(String s, int index, List<String> tmp) {
    if (index > s.length() || tmp.size() > 4) {
      return;
    }
    if (index == s.length() && tmp.size() == 4) {
      res.add(tmp.get(0) + "." + tmp.get(1) + "." + tmp.get(2) + "." + tmp.get(3));
      return;
    }
    for (int i = 1; i <= 3; i++) {
      if (index + i > s.length()) {
        continue;
      }
      if (isLegal(s.substring(index, index + i))) {
        tmp.add(s.substring(index, index + i));
        dfs(s, index + i, tmp);
        tmp.remove(tmp.size() - 1);
      }
    }
  }

  public Boolean isLegal(String t) {
    if ((t.charAt(0) == '0' && t.length() > 1) | Integer.parseInt(t) > 255) {
      return false;
    }
    return true;
  }
}
